package com.base.bfs;

import java.util.LinkedList;
import java.util.Queue;

public class OrangesRotting {
    /**
     * 994.腐烂的橘子
     * 在给定的网格中，每个单元格可以有以下三个值之一：
     *
     * 值0代表空单元格；
     * 值1代表新鲜橘子；
     * 值2代表腐烂的橘子。
     * 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
     *
     * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。
     *
     *
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/rotting-oranges
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    int[] mx = {1, -1, 0, 0};
    int[] my = {0, 0, -1, 1};

    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        boolean[][] seen = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                    seen[i][j] = true; //当前结点的橘子已经腐烂
                }
            }
        }
        int max = 0;  //初始时间
        while (!queue.isEmpty()) {
            int[] ints = queue.remove();
            int x = ints[0], y = ints[1];
            // 当前结点遍历周围结点
            for (int i = 0; i < 4; i++) {
                int xx = x + mx[i], yy = y + my[i];
                // 只能感染橘子的结点，不能感染非橘子结点  grid[xx][yy] == 1
                // 没有被感染 !seen[xx][yy]
                if (xx > -1 && yy > -1 && xx < m && yy < n && !seen[xx][yy] && grid[xx][yy] == 1) {
                    dist[xx][yy] = dist[x][y] + 1; // 感染了，因此时间过去了一分钟；
                    seen[xx][yy] = true;  //标志当前橘子已经被感染
                    grid[xx][yy] = 2;  // 改变橘子状态
                    queue.offer(new int[]{xx, yy}); //加入到感染者队列中
                    max = Math.max(dist[xx][yy], max);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1){
                    return -1;
                }
            }
        }


        return max;


    }

    public static void main(String[] args) {
        OrangesRotting orangesRotting = new OrangesRotting();
    }
}
